clear;
clc;

%% 生成图
numd = 100; %顶点数，不超过600
nume = 3; %边数，每个顶点出度不超过8
graph = graph(numd, nume);
for i = 1:numd
    for j = 1:numd
        if i == j
            continue;
        elseif graph(i,j) == 0;
            graph(i,j) = inf;
        end
    end
end

%% 生成子集
numv = 30; %子集大小，不超过50
vset = zeros(1,numv); %子集
for i = 1:numv
    temp = 1+floor(numd*rand());
    while sum(vset == temp) ~= 0
        temp = 1+floor(numd*rand());
    end
    vset(i) = temp;
end
vset = sort(vset);
startid = 1;
endid = 50;
f = fopen('request.csv','w'); %输出结果
fprintf(f, '%d,%d,', startid, endid);
for i = 1:numv-1
    fprintf(f, '%d|', vset(i));
end
fprintf(f, '%d\n', vset(numv));

%% Floyd算法
% 把子集的入度改为-999999
for i = 1:numv
    for j = 1:length(graph(:,vset(i)))
        if graph(j, vset(i)) ~= inf && j ~= vset(i)
           graph(j, vset(i)) = -99999;
        end
    end
end
tic;
% Floyd-Warshall算法
[D, path] = FloydSPR(graph);
toc;

% 从起始点通过生成的path走到终点
s = startid; t = endid;
L=zeros(0,0);
R=s;
while 1
    if s==t
        L=fliplr(L);
        L=[0,L];
        return
    end
    L=[L,D(s,t)];
    R=[R,path(s,t)];
    s=path(s,t);
end